package maps;

import java.util.HashSet;
import java.util.Iterator;

import java.util.Set;

public class MyHashMap<K, V> implements MyMap<K, V> {

	@SuppressWarnings("rawtypes")
	private SimpleEntry[] table;
	private static final int DEFAULT_INITIAL_CAPACITY = 16;
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;

	private int size;
	private int threshold;
	private final float loadFactor;

	public MyHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1) {
			throw new IllegalArgumentException();
		}
		this.loadFactor = loadFactor;
		this.threshold = (int) (loadFactor * initialCapacity);
		this.table = new SimpleEntry[initialCapacity];

	}

	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	private static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	private static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	@Override
	public void clear() {
		for (int i = 0; i < table.length; i++) {
			table[i] = null;
		}
		size = 0;

	}

	@Override
	public boolean containsKey(Object key) {
		if (key != null) {
			int hash = hash(key.hashCode());
			int index = indexFor(hash, table.length);

			@SuppressWarnings("unchecked")
			SimpleEntry<K, V> e = table[index];
			while (e != null) {
				if (e.hash == hash && (e.key == key || e.key.equals(key))) {
					return true;
				}
				e = e.next;
			}
			return false;
		} else {
			@SuppressWarnings("unchecked")
			SimpleEntry<K, V> e = table[0];
			while (e != null) {
				if (e.key == null) {
					return true;
				}
				e = e.next;
			}
			return false;
		}

	}

	@Override
	public boolean containsValue(Object value) {
		if (value != null) {
			int i = 0;
			while (i < table.length) {

				@SuppressWarnings("unchecked")
				SimpleEntry<K, V> e = table[i];
				while (e != null) {
					if (e.value.equals(value)) {
						return true;
					}
					e = e.next;
				}
				i++;
			}
			return false;
		}
		int i = 0;
		while (i < table.length) {

			@SuppressWarnings("unchecked")
			SimpleEntry<K, V> e = table[i];
			while (e != null) {
				if (e.value == null) {
					return true;
				}
				e = e.next;
			}
			i++;
		}
		return false;

	}

	@Override
	public V get(Object key) {
		if (key == null) {
			return getForNullKey();
		}
		int hash = hash(key.hashCode());
		int index = indexFor(hash, table.length);

		@SuppressWarnings("unchecked")
		SimpleEntry<K, V> e = table[index];
		while (e != null) {
			if (e.hash == hash && (e.key == key || e.key.equals(key))) {
				return e.value;
			}
			e = e.next;
		}
		return null;
	}

	private V getForNullKey() {
		@SuppressWarnings("unchecked")
		SimpleEntry<K, V> e = table[0];
		while (e != null) {
			if (e.key == null) {
				return e.value;
			}
			e = e.next;
		}
		return null;
	}

	@Override
	public boolean isEmpty() {

		return size == 0;
	}

	@Override
	public V put(K key, V value) {
		if (key == null) {
			return putForNullKey(value);
		} else {
			int h = hash(key.hashCode());
			int index = indexFor(h, table.length);

			@SuppressWarnings("unchecked")
			SimpleEntry<K, V> e = table[index];
			while (e != null) {

				if (h == e.hash && (e.key == key || e.key.equals(key))) {
					V oldValue = e.value;
					e.value = value;
					return oldValue;
				}
				e = e.next;
			}
			addSimpleEntry(h, index, key, value);
			return null;
		}

	}

	private V putForNullKey(V value) {
		@SuppressWarnings("unchecked")
		SimpleEntry<K, V> e = table[0];
		while (e != null) {
			if (e.key == null) {
				V oldValue = e.value;
				e.value = value;
				return oldValue;
			}
			e = e.next;
		}
		addSimpleEntry(0, 0, null, value);
		return null;

	}

	private void addSimpleEntry(int hash, int index, K key, V value) {
		@SuppressWarnings("unchecked")
		SimpleEntry<K, V> e = table[index];
		table[index] = new SimpleEntry<K, V>(hash, key, value, e);
		size++;
		if (size >= threshold) {
			resize(2 * table.length);
		}
	}

	private void resize(int capacity) {
		@SuppressWarnings("rawtypes")
		SimpleEntry[] newTable = new SimpleEntry[capacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (capacity * loadFactor);
	}

	@SuppressWarnings("unchecked")
	private void transfer(@SuppressWarnings("rawtypes") SimpleEntry[] newTable) {

		@SuppressWarnings("rawtypes")
		SimpleEntry[] oldTable = table;
		for (int i = 0; i < oldTable.length; i++) {

			SimpleEntry<K, V> e = oldTable[i];

			while (e != null) {

				SimpleEntry<K, V> next = e.next;

				int index = indexFor(e.hash, newTable.length);
				e.next = newTable[index];
				newTable[index] = e;
				e = next;
			}
		}

	}

	@Override
	public V remove(K key) {
		if (containsKey(key)) {
			if (key != null) {
				int hash = hash(key.hashCode());
				int index = indexFor(hash, table.length);
				@SuppressWarnings("unchecked")
				SimpleEntry<K, V> e = table[index];
				SimpleEntry<K, V> next = e.next;
				if (next == null) {
					if (e.hash == hash && (e.key.equals(key) || e.key == key)) {
						V value = e.value;
						e = null;
						size--;
						return value;
					}
				}
				while (next != null) {
					if (next.hash == hash
							&& (next.key.equals(key) || next.key == key)) {
						V value = next.value;
						e.next = next.next;

						next = null;
						size--;
						return value;
					}
					e = e.next;
					next = next.next;
				}
				return null;
			} else {
				@SuppressWarnings("unchecked")
				SimpleEntry<K, V> e = table[0];

				if (e.key == key) {
					V value = e.value;
					e = null;
					size--;
					return value;
				} else {
					return null;
				}

			}

		}
		return null;
	}

	@Override
	public int size() {

		return size;
	}

	public Set<MyHashMap.SimpleEntry<K, V>> entrySet() {
		if (!isEmpty()) {
			HashSet<MyHashMap.SimpleEntry<K, V>> set = new HashSet<MyHashMap.SimpleEntry<K, V>>();
			for (int i = 0; i < table.length; i++) {

				@SuppressWarnings("unchecked")
				SimpleEntry<K, V> e = table[i];
				while (e != null) {
					set.add(e);
					e = e.next;
				}

			}
			return set;
		}
		return null;
	}

	@Override
	public Iterator<MyHashMap.SimpleEntry<K, V>> entryIterator() {
		return new Iterator<MyHashMap.SimpleEntry<K, V>>() {
			Set<MyHashMap.SimpleEntry<K, V>> set = entrySet();
			Iterator<SimpleEntry<K, V>> iter = set.iterator();

			@Override
			public boolean hasNext() {

				return iter.hasNext();
			}

			@Override
			public SimpleEntry<K, V> next() {

				return iter.next();
			}

			@Override
			public void remove() {
				iter.remove();

			}
		};

	}

	static class SimpleEntry<K, V> implements MyMap.Entry<K, V> {

		K key;
		V value;
		SimpleEntry<K, V> next;
		final int hash;

		public SimpleEntry(int hash, K key, V value, SimpleEntry<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString() {

			return key + "=" + value;
		}

		@Override
		public K getKey() {

			return key;
		}

		@Override
		public V getValue() {

			return value;
		}

		@Override
		public Object setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

	}

}
